package com.example.algorithm.backtracing;

import java.util.*;

/**
 * 给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312"
 * 和 "192.168@1.1" 是 无效 IP 地址。
 *
 * 示例1：
 * 输入：s = "25525511135"
 * 输出：["255.255.11.135","255.255.111.35"]
 *
 * 示例2：
 * 输入：s = "0000"
 * 输出：["0.0.0.0"]
 *
 */
public class Leetcode93_RestoreIpAddresses {
    public static void main(String[] args) {

        String s =  "0000";
        s = "25525511135";
        List<String> strings = new Solution().restoreIpAddresses(s);
        strings.forEach(e -> System.out.println(e));
    }

    static class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> res = new ArrayList<>();
            if (s.length() < 4 || s.length() > 12) return res; // 字符串太短和太长都不可能组成IP地址
            Deque<String> singleRes = new ArrayDeque<>(4);
            backTrack(res, singleRes, 0, 0, s.length(), s);

            return res;
        }

        private void backTrack(List<String> res, Deque<String> singleRes,int index, int spiltTimes, int sLen, String s) {
            if (index == sLen && spiltTimes == 4) {
                res.add(String.join(".", singleRes));
                return;
            }
            // sLen - index 表示剩余的还未分割的字符串的位数
            if (sLen - index < 4 - spiltTimes
                    || sLen - index > 3 * (4 - spiltTimes)) // 对后面不可能组成IP地址的情况进行剪枝
                return;

            for (int i = 0; i < 3; i++) { // 每一个IP子段最多三位
                if (index + i >= sLen) break;

                String ipSegment = judgeIfIpSegment(s, index, index + i);

                if (!ipSegment.equals("")) {
                    singleRes.addLast(ipSegment);
                    backTrack(res, singleRes, index + i + 1, spiltTimes + 1, sLen, s);
                    singleRes.removeLast(); // 不满足时恢复状态
                }
            }
        }

        /**
         * 判断 s 的子区间 [left, right] 是否能够成为一个 ip 段
         * 如果能组成则返回对应的字符串，不能则返回""
         *
         * @param s
         * @param left
         * @param right
         * @return
         */
        private String judgeIfIpSegment(String s, int left, int right) {
            int len = right - left + 1;

            // 大于 1 位的时候，不能以 0 开头
            if (len > 1 && s.charAt(left) == '0') {
                return "";
            }

            int res = Integer.parseInt(s.substring(left, right + 1));
            return res > 255 ? "" : s.substring(left, right + 1);
        }
    }
}


